Speeding up LIKE with placeholders?

Is there any good way to speed up SQL that uses like and has placeholders?

Here's the scoop. I've got a system that uses a lot of pre-generated
SQL with placeholders in it. At runtime these SQL statements are
fired off (through the C PQexecParams function, if that matters) for
execution. No prepares or anything, just bare statements with $1 and
friends, with the values passed in as parameters. Straightforward,
and no big deal.

Unfortunately, performance is horrible. And when I mean horrible,
we're talking 6 orders of magnitude (101355.884 ms vs 0.267 ms) when
checked out via EXPLAIN ANALYZE. The slow version has the SQL defined
as a function with the parameters passed in, while the fast way has
the parameters substituted in, and the query plan for the slow
version notes that it's doing a sequential scan, while the fast
version uses one of the indexes. (And the field being LIKEd has a
b-tree index on it) The LIKE condition always has a constant prefix
-- it's 'S%' or 'S42343%' -- so it fits the index.

Now, I'd not be surprised for a generic function to do this, if the
plan is created when the function is created, and I can deal with
that. I'd figure, though, that since the parameters are being passed
into PQexecParams basically to get them out of band so I don't have
to deal with escaping, quoting, and suchlike things, that the
optimizer would look at things *after* the substitution was done.

Is there anything I can do to speed this up, short of doing the
parameter substitution myself and skipping PQexecParams here? (Which
I'd rather not, since it's a pain and somewhat error-prone (for me,
at least))
--
                Dan

--------------------------------------it's like this-------------------
Dan Sugalski                          even samurai
dan@sidhe.org                         have teddy bears and even
                                       teddy bears get drunk